#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>>result;
        vector<int>path;
        backtrack(candidates, target, result, path, 0);
        return result;
    }
private:
    void backtrack(vector<int>& candidates, int target,vector<vector<int>>&result,vector<int>&path, int start){
        if (target == 0) { result.push_back(path); return; }
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > target)break;
            path.push_back(candidates[i]);
            backtrack(candidates, target-candidates[i], result, path, i);
            path.pop_back();
        }
    }
};